#include<bits/stdc++.h>
#define N 410
#define int long long
#define il inline
#define ct const
#define dl double
#define pk push_back
#define fi first
#define se second
#define sit set<pii>::iterator
#define pii pair<int,int>
using namespace std;
il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
	}
	return x*f;
}
char f__[40];
il void write(int x){
	int cnt=0;
	if(x<0){
		putchar('-');x=-x;
	}
	if(!x) putchar('0');
	while(x){
		f__[cnt++]=x%10+'0';x/=10;
	}
	while(cnt) putchar(f__[--cnt]);
}
int head[N],nxt[N<<1],to[N<<1],t;
il void add(int u,int v){
    nxt[++t]=head[u];head[u]=t;to[t]=v;
    nxt[++t]=head[v];head[v]=t;to[t]=u;
}
int n,a[N],flag1=1,flag2=1,ans=-1e18,res;
bool vis[N];
il void dfs(int x){
    if(x>n){
        ans=max(ans,res);return;
    }
    for(int i=1;i<=n;++i) if(!vis[i]){
        res+=a[i];vis[i]=1;
        for(int j=head[i];j;j=nxt[j]) if(!vis[to[j]]) a[to[j]]+=a[i];
        dfs(x+1);
        res-=a[i];vis[i]=0;
        for(int j=head[i];j;j=nxt[j]) if(!vis[to[j]]) a[to[j]]-=a[i];
    }
}
signed main(){
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        if(u!=i+1||v!=i) flag1=0;
        if(u!=1||v!=i+1) flag2=0;
        add(u,v);
    }
    if(n<=10) dfs(1);
    else if(flag2){
        // cerr<<"ERROR";
        sort(a+2,a+1+n);
        res=a[1]*(n-1);
        for(int i=1;i<=n;++i) res+=a[i];
        int sum=a[1];
        for(int i=n;i>1;--i){
            res-=sum;res+=a[i]*(i-1);sum+=a[i];
            ans=max(ans,res);
        }
    }
    else if(flag1){
    }
    write(ans);
	return 0;
}